/*
	结点带权路径长度:从该结点到树的根结点之间的路径长度与
	                结点的权的乘积
	权值:各种开销、代价、频度等抽象称呼

	树的带权路径长度:树中所有叶子结点的带权路径长度之和,
		记作:
		WPL = w1*l1 + w2*l2+...+wn*ln

	Huffman树:具有n个叶子结点(每个结点的权值为wi)的二叉树不止
	一颗,但在所有的这些二叉树中,必定存在一颗WPL值最小的树,称为
	Huffman树(最优树)
*/

/*
	huffman树没有度为一的结点
	一颗有n个叶子结点的huffman树共有2n-1个结点,可存储在大小为2n-1
	的一维数组中

	没有度为1的结点又称为正则二叉树
*/

#include<stdio.h>
#define MAX_NODE 200

typedef struct huffman
{
	unsigned Weight;
	unsigned int Parent,Lchild,Rchild;
}Huffman;

void CreateHuffman(unsigned n, Huffman Huffman[], unsigned m)
{//创建一个叶子结点数为n的huffman树,m结点总数
	unsigned int w;
	int k,j;
	for(k = 1; k < m; k++)
	{
		if (k <= n)
		{
			printf("\n输入:");
			scanf("%d," &w);
			Huffman.Weight = w;
		}
		else 
			Huffman[k].weight = 0;
		/*非叶子结点没有权值*/

		Huffman[k].Parent = Huffman[k].Lchild = Huffman[k].Rchild = 0
	}

	for(k = n+1;k < m; k++)
	{
		unsigned w1 = 32767, w2 = w1;
		/*w1,w2分别保存权值最小的两个权值*/
		int p1 = 0; p2 = 0;
		/*p1,p2保存两个最小权值的下标*/
		for(j = 1; j <= k - 1; j++)
		{
			if(Huffman[k].Parent == 0)//未合并的结点
			{
				if (Huffman[j].Weight < w1)
				{//找出前k个里w最小的序号给p1,权值给w1
					w2 = w1;
					p2 = p1;

					w1 = Huffman[j].Weight;
					p1 = j;
				}
				else if (Huffman[j].Weight < w2)
				{//找到另一个最小的
					w2 = Huffman[j].Weight;
					p2 = j;
				}
			}
		}

		Huffman[k].Lchild = p1;
		Huffman[k].Rchild = p2;
		Huffman[k].Weight = w1 + w2;
		Huffman[p1].Parent = k;
		Huffman[p2].Parent = k;

	}
}

void Huffcoding(unsigned n, Huffman Huffman[], unsigned m)
{/*m应为最大长度加1,n+1*/
	int k,sp,fp;
	char *cd,*HC[m];
	cd = (char*)malloc(m*sizeof(char));
	cd[n] = '\0';
	/*编码结束的标志*/
	for(k = 1; k < n + 1; k++)
	{
		sp = n;
		p = k;
		fp = Huffman[k].Parent;

		for(;fp != 0; p = fp, fp = Huffman[p].Parent)
		{/*从叶子结点到根逆向求编码*/
			if (Huffman[fp].Parent == Lchild)
				cd[--sp] = '0';
			else
				cd[--sp] = '1';

			HC[K] = (char *)malloc((n-sp)*sizeof(char));

			trcpy(HC[k],&cd[sp]);
		}
	}
	free(cd);
}